package tree.leveltraversal;

import tree.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Classname : AverageOfLevelsInBinaryTree
 * @Description :
 * <a href="https://leetcode.cn/problems/average-of-levels-in-binary-tree/">637. 二叉树的层平均值</a>
 * @Author : chentianyu
 * @Date 2023/1/7 22:28
 */


public class AverageOfLevelsInBinaryTree {

    /**
     * 队列实现广度优先搜索
     *
     * @param root
     * @return
     */
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> average = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            long sum = 0;  // 注意每层累加可能超出整型范围，因此使用长整型
            for (int i = 0; i < size; i++) {
                TreeNode cur = q.poll();
                sum += cur.val;
                if (cur.left != null) q.offer(cur.left);
                if (cur.right != null) q.offer(cur.right);
            }
            average.add(sum * 1.0 / size);
        }
        return average;
    }
}
